#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//声明一个单链表类型结构体
typedef int DATA_TYPE;//数据类型
typedef struct singlelinklist
{
    DATA_TYPE data;//数据域      
    struct singlelinklist *next;//指针域  
}Lnode,*p_linklist;

//创建一个空链表
p_linklist list_Create();

//尾插
int list_tail_insert(p_linklist H, DATA_TYPE value);

//排序
int list_Sort(p_linklist H);

//链表合并
p_linklist list_Merge(p_linklist H1 , p_linklist H2);

// 遍历链表
int list_show(p_linklist H);

//销毁链表
int list_free(p_linklist *H);

int main(int argc, char const *argv[])
{
    p_linklist HEAD1=NULL;
    p_linklist HEAD2=NULL;
    HEAD1=list_Create();
    HEAD2=list_Create();
     //尾插
     printf("HEAD1尾插法插入8,5,6,1\n");
     list_tail_insert(HEAD1,8);
     list_tail_insert(HEAD1,5);
     list_tail_insert(HEAD1,6);
     list_tail_insert(HEAD1,1);
    //遍历
    list_show(HEAD1);
    printf("排序后");
    list_Sort(HEAD1);
    list_show(HEAD1);
    printf("\n");

    //尾插
    printf("HEAD2尾插法插入4,2,7,3\n");
    list_tail_insert(HEAD2,4);
    list_tail_insert(HEAD2,2);
    list_tail_insert(HEAD2,7);
    list_tail_insert(HEAD2,3);
    //遍历
    list_show(HEAD2);
    printf("排序后");
    list_Sort(HEAD2);
    list_show(HEAD2);
    printf("\n");

    printf("顺序合并HEAD1和HEAD2\n");
    p_linklist HEAD = list_Merge(HEAD1,HEAD2);
    list_show(HEAD);
    printf("\n");

    return 0;
}

//创建一个空链表
p_linklist list_Create()
{
    p_linklist head=NULL;//定义一个头结点  是一个空指针
    head=(p_linklist)malloc(sizeof(Lnode));//向堆区申请一段空间
    //判断是否申请空间成功
    if(head==NULL)
    {
        printf("malloc faild\n");
        return NULL;
    }
    //由于我们创建的是一个带头结点的链表   头结点将不会用来存储数据
    head->data=0;
    head->next=NULL;
    return head;
}

int list_tail_insert(p_linklist H, DATA_TYPE value)
{
    //链表是否存在
    if(H==NULL)
    {
        printf("list is error\n");//链表不存在
        return -1;
    }
    //创建一个新的结点
    p_linklist newnode =(p_linklist)malloc(sizeof(Lnode)) ; 
    if(newnode==NULL)
    {
        printf("newnode malloc faild\n");
        return -1;
    }
    //将新数据给新结点
    newnode->data=value;
    newnode->next=NULL;//指针域为空
    //找到尾  遍历
    p_linklist p_head=H;//从头结点开始遍历
    while(p_head->next!=NULL)
    {
        p_head=p_head->next;
    }
    //当前phead指向的是尾节点
    p_head->next=newnode;//建议连接

    return 0;
}

//冒泡排序
int list_Sort(p_linklist H)
{
    //如果链表为空或者只有一个数据则直接返回
    if(H == NULL || H->next == NULL)
    {
        printf("list is NULL or too short");
        return -1;
    }
    //swap用来标记一次排序中是否交换过数据
    int swap = 0;
    //lastsort表示记录上次排序的最后一个确定值的位置，current表示当前位置
    p_linklist  lastsort = NULL, current;
    do
    {   //每次循环重置交换标记
        swap = 0;
        //重置节点位置
        current = H->next;
        //内循环用来判断交换
        while (current->next != lastsort)
        {
            if (current->data > current->next->data)
            {
                //只对data数值做交换
                int temp = current->data;
                current->data = current->next->data;
                current->next->data = temp;
                //交换标签置1
                swap = 1;
            }
            //移动位置
            current = current->next;
            
        }       
        // 记录最后一次交换的位置，优化性能
        lastsort = current;
    } while (swap);
    
    return 0;
}
//合并两个有序链表
// p_linklist list_Merge(p_linklist H1 , p_linklist H2)
// {
//     //递归终止条件，如果其中一个链表的成员排序完成则将另外一个链表的剩下成员返回
//     if (H1 == NULL) return H2;
//     if (H2 == NULL) return H1;

//     if(H1->data < H2->data)
//     {
//         H1->next = list_Merge(H1->next,H2);
//         return H1;
//     }else
//     {
//         H2->next = list_Merge(H1,H2->next);
//         return H2;
//     }
// }

//合并两个有序链表
p_linklist list_Merge(p_linklist H1, p_linklist H2) 
{
    // 创建临时的头节点
    p_linklist dummy = (p_linklist)malloc(sizeof(Lnode));
    dummy->next = NULL;
    p_linklist tail = dummy;
    
    p_linklist p1 = H1->next;  // 跳过H1的头节点
    p_linklist p2 = H2->next;  // 跳过H2的头节点
    
    // 合并两个链表
    while (p1 != NULL && p2 != NULL) {
        if (p1->data <= p2->data) {
            tail->next = p1;
            p1 = p1->next;
        } else {
            tail->next = p2;
            p2 = p2->next;
        }
        tail = tail->next;
    }
    
    // 连接剩余部分
    tail->next = (p1 != NULL) ? p1 : p2;
    
    // 保留H1的头节点，连接合并后的链表
    H1->next = dummy->next;
    free(dummy);  // 释放临时头节点
    
    // 释放H2
    free(H2);
    
    return H1;
}

// 遍历链表
int list_show(p_linklist H)
{
    //判空 判断链表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
        
    }
    //因为是带头结点的单链表
    if(H->next==NULL)
    {
        printf("list is empty\n");
        return -1;
    }
    printf("遍历: ");
    //遍历
    p_linklist phead=H->next;//可以从下一个结点开始遍历
    while(phead)
    {
        printf("%d ",phead->data);
        phead=phead->next;
    }
    printf("\n");
    return 0;

}
int list_free(p_linklist *H)
{
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    p_linklist phead=(*H)->next;//指向数据结点
    p_linklist qhead=NULL;
    while(phead!=(*H))
    {
        qhead=phead->next;//保存要删除的结点的下一个结点
        //删除这个结点
        memset(phead,0,sizeof(Lnode));
        free(phead);
        //更新下一次要销毁的结点
        phead=qhead;
    }
    //释放 （*H）  就是头结点
    memset((*H),0,sizeof(Lnode));
    free((*H));
    *H=NULL;
    return 0;
}